Display Problems

Imagination is more important than knowledge... Albert Einstein

Guess is more important than calculation --- Knowhowacademy.com

Numbers - Factor and Multiple

For COMPETITION
Number of Total Problems: 21.
FOR PRINT ::: (Book)

Problem Num : 21

From : AMC10

Type:

Section:Numbers

Theme:
Adjustment# : 0

Difficulty: 1

For $k > 0$ , let $I_k = 10ldots 064$ , where there are $k$ zeros between the $1$ and the $6$ . Let $N(k)$ be the number of factors of $2$ in the prime factorization of $I_k$ . What is the maximum value of $N(k)$ ?
$extbf{(A)} 6qquad extbf{(B)} 7qquad extbf{(C)} 8qquad extbf{(D)} 9qquad extbf{(E)} 10$
'

Category Factor and Multiple

Analysis

Solution/Answer
The number $I_k$ can be written as $10^{k+2} + 64 = 5^{k+2}cdot 2^{k+2} + 2^6$ .
For $kin{1,2,3}$ we have $I_k = 2^{k+2} left( 5^{k+2} + 2^{4-k} ight)$ . The first value in the parentheses is odd, the second one is even, hence their sum is odd and we have $N(k)=k+2leq 5$ .
For $kgeq 5$ we have $I_k=2^6 left( 5^{k+2}cdot 2^{k-4} + 1 ight)$ . For $k>4$ the value in the parentheses is odd, hence $N(k)=6$ .
This leaves the case $k=4$ . We have $I_4 = 2^6 left( 5^6 + 1 ight)$ . The value $5^6 + 1$ is obviously even. And as $5equiv 1 pmod 4$ , we have $5^6 equiv 1 pmod 4$ , and therefore $5^6 + 1 equiv 2 pmod 4$ . Hence the largest power of $2$ that divides $5^6+1$ is $2^1$ , and this gives us the desired maximum of the function $N$ : $N(4) = oxed{7}$ .

Alternate Solution

Notice that 2 is a prime factor of an integer $n$ if and only if $n$ is even. Therefore, given any sufficiently high positive integral value of $k$ , dividing $I_k$ by $2^6$ yields a terminal digit of zero, and dividing by 2 again leaves us with $2^7 * a = I_k$ where $a$ is an odd integer. Observe then that $oxed{7}$ must be the maximum value for $N(k)$ because whatever value we choose for $k$ , $N(k)$ must be less than or equal to 7.

Answer:

Array ( [0] => 7905 ) 211 2 3